/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/backpack
   @Language: C++
   @Datetime: 16-02-09 05:42
   */


// Method 1, Time O(n*m), Space O(n*m), Time 553ms
class Solution {
public:
	/**
	 * @param m: An integer m denotes the size of a backpack
	 * @param A: Given n items with size A[i]
	 * @return: The maximum size
	 */
	int backPack(int m, vector<int> &A) {
		// write your code here
		vector<vector<int> > dp(A.size(), vector<int>(m+1,0));
		for(int i=1; i<=m; ++i)
			dp[0][i]=i<A[0]?0:A[0];
		for(int i=1; i<A.size(); ++i){
			for(int j=1; j<=m; ++j){
				if (j<A[i]) dp[i][j]=dp[i-1][j];
				else dp[i][j]=max(dp[i-1][j],dp[i-1][j-A[i]]+A[i]);
			}
		}
		return dp[A.size()-1][m];
	}
};


// Method 2, Time O(n*m), Space O(m), Time 352ms
class Solution {
public:
	/**
	 * @param m: An integer m denotes the size of a backpack
	 * @param A: Given n items with size A[i]
	 * @return: The maximum size
	 */
	int backPack(int m, vector<int> &A) {
		// write your code here
		vector<int> dp(m+1,0);
		for(int i=0; i<A.size(); ++i)
			for(int j=m; j; --j)
				if (j>=A[i]) dp[j]=max(dp[j],dp[j-A[i]]+A[i]);
		return dp[m];
	}
};
